package code1.linkedlist;

/**
 * 原题链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
 */
public class P19 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //删除倒数第n个节点,快慢指针法
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode myHead=new ListNode(0);
        myHead.next=head;
        ListNode fast=myHead;
        ListNode slow=myHead;
        //快指针先走n+1步，快慢指针相差n+1步
        for(int i=0;i<=n;i++){
            fast=fast.next;
        }
        //快慢指针同步走，直至末尾，这样慢指针正好指向倒数第n个节点的前一个节点
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return myHead.next;
    }


}
